1. Field of the Invention
This invention relates to a memory apparatus, specifically, a cache memory apparatus, which receives data consecutively and erases the data in order of the low priority according to a specific algorithm. This invention improves a hit ratio especially in the data base processing system by changing the priority of the disk caches.
2. Description of the Related Art
It is effective to improve the speed of accessing to the storage area which has a large capacity as a means for improving the system efficiency. In a conventional system, a high-speed memory apparatus called a cache memory is provided between a CPU and accessing devices, for example a slow-speed memory apparatus, a disk drive, and so on. Such high-speed memory apparatus is priced high. Therefore, it is difficult to have a capacity large enough to cover all the accessing storage area, so the cache memory apparatus generally has a small capacity. Transmission between such a memory apparatus and the storage area is performed in fixed block units. In case that the cache memory apparatus has data for accessing, the data can be accessed in a short access time. In case that the memory apparatus does not have data for accessing, the data should be taken from the storage area. As the possibility to have data for accessing in the memory apparatus gets higher, the efficiency of the total system increases. Therefore, it is desirable that the cache memory apparatus should be so managed that it erases data block having lower priority for enabling a new block to be written.
In such a memory apparatus, Least Recently Used (LRU) algorithm is adopted as a means for giving priority.
This algorithm is based on a concept that some elements of a program in a main memory are repeatedly used at the execution time of the program. Accordingly, the efficiency of the program at the execution time increases if the repeatedly used elements always exist in a cache memory apparatus.
As to a disk drive, the algorithm is based on a concept that access requests to data have a tendency to concentrate on a specific block. On the other hand, in some services, all the blocks on the disk drive are accessed impartially. When the LRU algorithm is adopted in this case, probability of accessing data blocks in the cache memory apparatus is reduced.
Further, an index is used as a method of accessing a large amount of data with high-speed. For example, in the data base processing system, in a fixed processing, there is a tendency that specific data items to be read out are limited. It is possible to set up the index about these items in advance. For example, if an index is set up to an item "man-number", it is possible to perform high-speed retrieval only by using the index without checking the data file.
On the other hand, in a non-fixed processing, there is a tendency that an arbitrary retrieval is performed so as to accept a demand which occurs at random. Therefore, it is difficult and not practical to set up the index previously corresponding to the demand. As a result, it is needed to search all the data recorded in one table or file so as to retrieve the data satisfying the indicated retrieval condition.
The probability of the requested data being in the cache memory is called hit ratio.
In the data base processing, especially in the non-fixed processing, data access is likely performed to the same table repeatedly. Data on the table are stored in the disk cache area on the memory apparatus from the disk drive. In case that the table is small enough to be included in the disk cache area, it is possible to access data at high speed because the disk cache can hit data except for the first data access. But when the size of the table goes over the disk cache area, it is possible that the cache area is ineffective.
For example, a command based on Structured Query Language (SQL) may be issued to the data base in a non-fixed processing. SQL is an operation language for performing the process of retrieval, update, and delete on the data base. As described before, in a non-fixed processing, there are many cases that all data in the specific table are searched without the index. On the other hand, as described before, the cache memory is designed based on the idea that data accesses are partial or clustered on some data on the cache memory. That is, if the priority is given to the partial data based on the clustered data accesses, the existing probability of frequently accessed data in the disk cache increases. Therefore, in case that such a precondition is not adapted, in other words, in case that the access is not partial nor clustered, the disk cache itself sometimes comes to be useless.
An explanation will be made hereinafter, referring to the case that all the data blocks on the disk cache are accessed, in connection with the attached figures.
FIG. 23 is a block diagram illustrating a configuration of a conventional memory apparatus. In the figure, a cache memory 10 and a cache management information 3 are provided. A means for giving priority 20 gives priority to the data stored in the cache memory 10. A means for erasing 40 erases data orderly from the data with lower priority given by the means for giving priority 20. A memory controller 150 controls these elements.
FIG. 24 illustrates the operation of a conventional disk cache area. To simplify a description, an explanation is made for the case that this cache memory adopts the LRU algorithm.
In FIG. 24, cache memory area consists of eight blocks, while the disk drive consists of ten blocks. Now there will be explained the case that data D0 to D9 from the disk drive are consecutively stored to the cache memory. In (a) of FIG. 24, data D0 to D7 are already stored to the cache memory area. When this data was stored from the disk drive to the cache memory area, the cache did not hit data.
Next, when data D8 is read from the disk drive as shown in (b) of FIG. 24, the oldest data D0 in (a) of FIG. 24 is discarded and replaced with data D8. Further, when data D9 is read from the disk drive, the oldest data D1 shown in (b) of FIG. 24 is discarded and replaced with data D9 as shown in (c) of FIG. 24. Further, when data D0 is then read from the disk drive, the oldest data D2 shown in (c) of FIG. 24 is discarded and replaced with D0. When data D1 are read from the disk drive, the oldest data D3 in (d) of FIG. 24 is discarded and replaced with data D1. Thus, in case that data from the disk drive are stored repeatedly in order, the cache does not hit data at all and the disk cache is useless.
As has been described, if data in a single table is accessed repeatedly in a data base processing system, in a conventional cache memory, when the size of the table is larger than the cache memory area, the cache memory does not hit data at all because the old data in the disk cache area is replaced with the data at the end of the table. In non-fixed processing, especially, if accesses to the same table are made repeatedly, the cache memory generally is not effective, thus decreasing the efficiency of the whole system.